
/*
前缀树
*/

public class TireTree {

    public static class Node{
        public int pass;
        public int end;
        public Node[] nexts;
        public Node(){
            this.pass = 0;
            this.end = 0;
            this.nexts = new Node[26];
        }
    }
    private Node root = new Node();

    public void insertTireTree(String word){
        if(word==null||word.length()==0){
            return;
        }
        Node node = root;
        node.pass++;
        char[] str = word.toCharArray();
        int index = 0;
        for(int i =0;i<str.length;i++){
            index = str[i]-'a';
            if(node.nexts[index]==null){
                node.nexts[index] = new Node();
            }
            node = node.nexts[index];
            node.pass++;
        }
        node.end++;
    }

    public int searchTireTree(String word){
        if(word==null||word.length()==0){
            return 0;
        }
        Node node = root;
        char str[] = word.toCharArray();
        int index = 0;
        for(int i =0;i<str.length;i++){
            index = str[i]-'a';
            if(node.nexts[index]==null){
                return 0 ;
            }
            node = node.nexts[index];
        }
        return node.end;
    }

    public static void main(String[] args) {
        TireTree tireTree = new TireTree();
        tireTree.insertTireTree("ab");
        tireTree.insertTireTree("ab");
        tireTree.insertTireTree("abcd");
        tireTree.insertTireTree("ab");
        System.out.println( tireTree.searchTireTree("abcd"));
    }
}
